#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"


typedef char STDataType;
typedef struct Stack
{
    STDataType* arr;
    int top, capacity;
} ST;
void StackInit(ST* ps)
{
    assert(ps);
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int NewCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
        STDataType* temp = (STDataType*)realloc(ps->arr, NewCapacity * sizeof(STDataType));
        ps->arr = temp;
        ps->capacity = NewCapacity;
    }
    ps->arr[ps->top++] = x;
}
bool StackEmpty(ST* ps)
{
    assert(ps);
    return (ps->top == 0);
}
void StackPop(ST* ps)
{
    assert(!StackEmpty(ps));
    ps->top--;
}
STDataType StackTop(ST* ps)
{
    assert(!StackEmpty(ps));
    return ps->arr[ps->top - 1];
}
void StackDestroy(ST* ps)
{
    assert(ps);
    if (ps->arr != NULL)
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

bool isValid(char* s)
{
    ST st;
    StackInit(&st);
    char* pi = s;
    while (*pi != '\0')
    {
        if ((*pi == '(') || (*pi == '{') || (*pi == '['))
        {
            StackPush(&st, *pi);
        } 
        else
        {
            if (StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            STDataType top = StackTop(&st);
            if ((top == '(' && *pi != ')')
                || (top == '{' && *pi != '}')
                || (top == '[' && *pi != ']'))
            {
                StackDestroy(&st);
                return false;
            }
            StackPop(&st);
            pi++;
        }
    }
    bool ret = (StackEmpty(&st)) ? true : false;
    StackDestroy(&st);
    return ret;
}

int main()
{
    char s[] = "()[]{}";
    isValid(&s);
	return 0;
}

